Time Complexity (Asymptotic notation )

= = = = = = = = = = = =

• $O()$ BigO / upper bound

    已知 f(n) 想找一 cg(n) 十分貼近但是都在它上面
  

  $n_0$ 是臨界值 當 $n$ 大於等於此皆符合

• $Ω()$ Omega / lower bound

相反

• $Θ()$ 西塔

找到滿足上面兩個式子的就是了!

= = = = = = = = = = = =

• 隨便舉例 : $6n^3 不等於 Θ(n^2)$

  //$因為BigO那邊不能滿足，都n^3了不可能找n^2$

• a是b的O()，b就是a的Θ() //畫個圖就知道了

• 題目常出 : $找 O()再找 Ω() 最後再找 Θ()$

@ 卻不知道Θ()裡面是n的多少
    a>0時直接找次方最大的那個做 O() Ω() Θ()
        不可能負數在最大項數，因為不可能有程式跑的時間小於0

兩個要兜起來前要注意O()和Ω()是不是都是n^3若不是就找不到

較少討論

• ο-notation 小O

Trichotomy 三分法

Not all functions are asymptotically comparable

sin落在-1到1
n根本不知道怎麼和他們比阿!如何做比較?
但是就此例中，題目最大為2，n^2其實找的到O()和Ω()n0
只是沒有Θ()